import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import static com.sun.deploy.net.MessageHeader.merge;

//完成八大排序
public class Sort {
    /**
     * 插入排序（从小到大顺序排序）
     * 时间复杂度：O(N)-O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @param array
     */
    public static void insertSort(int[] array) {
        //插入排序需要从第二个元素开始
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            //设置j为i的前一个数据
            int j = i - 1;
            //之后在j下标之前向前寻找，若找到比其更小的j下标，将其插入这个位置后面
            for (; j >= 0; j--) {
                if (array[j] > temp) {
                    array[j + 1] = array[j];
                    array[j] = temp;
                } else {
                    break;
                }
            }
        }
    }


    /**
     * 希尔排序
     * 时间复杂度：不确定，但是这里的时间复杂度会在循环的过程中会有一个两头都为O(N),中间有个未知高度的时间复杂度
     * 大致认为是O（N^1.3-N^1.5）
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void shellSort(int[] array) {
        //将数组元素整体分为gap组
        int gap = array.length / 2;
        while (gap > 0) {
            shell(array, gap);
            gap /= 2;
        }
    }

    private static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int temp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > temp) {
                    array[j + gap] = array[j];
                    array[j] = temp;//(这段代码可以转换为array[j+gap] = temp;并将其放在该层for循环外面)
                } else {
                    break;
                }
            }
        }
    }


    /**
     * 选择排序（可以一次选取两个数字来加快排序速度，但是时间复杂度不会变）
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array（用10-1测试）
     */
    public static void selectSort1(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int min = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[min]) {
                    min = j;
                }
            }
            Swap(array, i, min);
        }
    }

    public static void selectSort2(int[] array) {
        //首先定义左右两个下标,保证left的左边和right的右边都是排好序的
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            //定义一趟的最大值和最小值的下标
            int maxIndex = right;
            int minIndex = left;
            for (int i = left; i <= right; i++) {
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
            }
            Swap(array, left, minIndex);
            Swap(array, right, maxIndex);
            left++;
            right--;
        }

    }

    private static void Swap(int[] array, int x, int y) {
        int temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }

    /**
     * 堆排序 时间复杂度: O(N*logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void heapSort(int[] array) {
        //要想使用堆排序，需要确定使用大根堆还是小根堆（因为是要求从小到大排序，所以采用大根堆）
        int child = array.length - 1;
        createHeap(array, child);
        int end = array.length - 1;
        while(end > 0){
            Swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }


    private static void createHeap(int[] array,int child) {
        //建立一个大根堆
        for (int parent = (child - 1) / 2; parent >= 0; parent--) {
            siftDown(array,parent,array.length);
        }
    }
    //这里的length必须要有，因为这可以限定调整的范围
    private static void siftDown(int[] array, int parent,int length) {
        int child = parent * 2 + 1;
        while (child < length) {
            if (child + 1 < length && array[child] < array[child + 1]) {
                child++;
            }
            if (array[child] > array[parent]) {
                Swap(array, parent, child);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

    /**
     * 冒泡排序 时间复杂度：O(N^2)
     * 空间复杂度：O（1）
     */
    public static void bubbleSort(int[] array) {
        for(int i = 0; i < array.length; i++){
            boolean flag = true;
            for(int j = 0;j < array.length - i - 1; j++){
                if(array[j] > array[j+1]){
                    Swap(array, j, j+1);
                    flag = false;
                }
            }
            if(flag){
                break;
            }
        }
    }


    /**
     * 快速排序
     * 时间复杂度：O(N*logN)~O(N^2)
     * 空间复杂度：O(N)
     * 稳定性：不稳定
     */
    public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }
    private static void quick(int[] array, int left, int right) {
        if(left >= right){
            return;
        }
        //先找到一个节点，使得其左边都比其小，右边都比其大
        int par = partition3(array,left,right);
        quick(array, left, par-1);
        quick(array, par+1, right);
    }

    //Hoare法
    private static int partition(int[] array, int start, int end) {
        if(start == end){
            return start;
        }
        //先寻找一个标记(可以将第一个数据作为标记)
        int pivot = array[start];
        int key = start;
        while(start < end){
            //从右边找到一个比privot小的数据停下（必须先右后左，因为如果先左可能将大于）
            while(start < end && array[end] >= pivot){
                end--;
            }
            //从左边找到一个比pivot大的数据(这里的=必须加上，因为如果不加则可能会陷入死循环，此时的start和end对应的数据都等于privot)
            while(start < end && array[start] <= pivot){
                start++;
            }
            //将找到的两个数据交换
            Swap(array, start, end);
        }
        //最后将标记的数据和最终start和left重叠的数据交换
        Swap(array,key,start);
        return start;
    }


    //挖坑法
    private static int partition2(int[] array, int start, int end){
        if(start == end){
            return start;
        }
        int pivot = array[start];
        while(start < end){
            //同样先判断右边，在判断左边
            while(start < end && array[end] >= pivot){
                end--;
            }
            array[start] = array[end];
            while(start < end && array[start] <= pivot){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = pivot;
        return start;
    }

    //前后指针法
    private static int partition3(int[] array, int start, int end){
        if(start == end){
            return start;
        }
        int prev = start;
        int cur = start+1;
        while(cur <= end){
            if(array[cur] < array[start] && array[++prev] != array[cur]){
                Swap(array, prev, cur);
            }
            cur++;
        }
        Swap(array,prev,start);
        return prev;
    }

    //优化快速排序（三数取中法）
    //三数取中是为了防止极端情况出现导致无法分割数组
    private static void quick2(int[] array, int left, int right){
        if(right - left <= 10){
            insertSortRange(array, left, right);
            return;
        }
        //首先找到三个数中间大小的数
        int index = midNum(array,left,right);
        Swap(array,left,index);
        int par = partition2(array,left,right);
        quick2(array,left,par-1);
        quick2(array,par+1,right);
    }
    private static int midNum(int[] array, int start, int end){
        int mid = (start + end) / 2;
        if(array[start] > array[end]){
            if(array[mid] > array[start]){
                return start;
            } else if (array[mid] > array[end]) {
                return mid;
            }else {
                return end;
            }
        }else {
            if(array[mid] > array[end]){
                return end;
            } else if (array[mid] > array[start]) {
                return mid;
            }else {
                return start;
            }
        }
    }

    private static void insertSortRange(int[] array, int start, int end){
        //插入排序需要从第二个元素开始
        for (int i = start; i <= end; i++) {
            int temp = array[i];
            //设置j为i的前一个数据
            int j = i - 1;
            //之后在j下标之前向前寻找，若找到比其更小的j下标，将其插入这个位置后面
            for (; j >= start; j--) {
                if (array[j] > temp) {
                    array[j + 1] = array[j];
                    array[j] = temp;
                } else {
                    break;
                }
            }
        }
    }


    //非递归快速排序
    public static void quickSortNor(int[] array){
        //设置一个栈存放左右边界
        Stack<Integer> stack = new Stack<Integer>();
        int left = 0;
        int right = array.length - 1;
        //先将首尾放入栈中
        stack.push(left);
        stack.push(right);
        while(!stack.isEmpty() && left <= right){
            //将左右边界取出来
            right = stack.pop();
            left = stack.pop();
//            //首先找到三个数中间大小的数
//            int index = midNum(array,left,right);
//            Swap(array,left,index);
            //找关键节点（标记）
            int pivot = partition2(array,left,right);
            //检查左右两边是否都有两个以上元素
            if(pivot > left+1){
                stack.push(left);
                stack.push(pivot-1);
            }
            //只有存在两个以上元素时才需要排序，只有一个元素时不需要排序
            if(pivot < right - 1){
                //找到之后将两个左右边界都放入栈中(放的时候先放左后放右，拿的时候先拿右后拿左)
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

    /**
     * 归并排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(N)
     * 稳定性：稳定
     * @param array
     */
    public static void mergeSort(int[] array){
        int left = 0;
        int right = array.length - 1;
        mergeSortChild(array,left,right);
    }

    private static void mergeSortChild(int[] array, int start, int end){
        //首先需要将数组拆分开
        if(start >= end){//防御型编程
            return;
        }
        int mid = (start + end) / 2;
        //将两个以上的元素一半一半进行拆分
        mergeSortChild(array,start,mid);
        mergeSortChild(array,mid+1,end);
        //拆分好以后开始合并
        merge(array,start,mid,end);
    }

    //至少有两个元素才可以进入这个方法进行排序
    //这个方法的作用就是将start到end的元素排序后放入对应位置的数组中
    private static void merge(int[] array, int start, int mid, int end) {
        //首先创建一个数组用来存放元素
        int[] tmpArray = new int[end-start+1];
        //将两个区块中的左右下标都记录下来
        int s1 = start;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = end;
        int k = 0;
        while(s1 <= e1 && s2 <= e2){
            if(array[s1] <= array[s2]){
                tmpArray[k++] = array[s1++];
            }else {
                tmpArray[k++] = array[s2++];
            }
        }
        //结束后有一个先出去，之后将另一个有序数组依次放到临时数组中即可
        if(s1 > e1){
            while(s2 <= e2){
                tmpArray[k++] = array[s2++];
            }
        }
        if(s2 > e2){
            while(s1 <= e1){
                tmpArray[k++] = array[s1++];
            }
        }
        //最后将临时数组中的元素拷贝到原来数组当中，这样赋值也可以保证不会影响到其他组
        for(int i = 0; i < k; i++){
            array[i+start] = tmpArray[i];
        }
    }

    /**
     * 非递归实现归并排序
     * @param array
     */
    public static void mergeSortNor(int[] array){
        //非递归的情况下只需要合并，无需拆分步骤
        //设置每组有gap个成员，每次合并都将其乘以2
        int gap = 1;
        //外层循环表示合并几次
        while(gap < array.length){
            for(int i = 0;i < array.length;i=i+gap*2){
                int start = i;
                int mid = start + gap - 1;
                //防止下标越界，数组内的数据个数可能会在分好组后最后一组不足gap个
                if(mid >= array.length){
                    mid = array.length - 1;
                }
                int end = mid + gap;
                if(end >= array.length){
                    end = array.length - 1;
                }
                merge(array,start,mid,end);
            }
            gap *= 2;
        }
    }


    /**
     *计数排序
     * 时间复杂度：O(MAX(N,范围))
     * 空间复杂度O(范围)
     * @param array
     */
    public static void countSort(int[] array){
        //首先找到数组元素的最大值和最小值
        int max = array[0];
        int min = array[0];
        for(int i = 1;i < array.length;i++){
            if(array[i] > max){
                max = array[i];
            }
            if(array[i] < min){
                min = array[i];
            }
        }
        //利用最大值和最小值的差建立一个计数数组
        int[] countArray = new int[max-min+1];
        //遍历原数组
        for (int i = 0; i < array.length; i++) {
            countArray[array[i]-min]++;
        }
        //遍历计数数组之后再将其下标加上min依次放入原数组
        int k = 0;
        for(int i = 0; i < countArray.length; i++){
            while(countArray[i]-- > 0){
                array[k++] = i+min;
            }
        }
    }


}